home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CBASE102.ARJ / BTREE.H < prev    next >
Text File  |  1991-09-23  |  6KB  |  189 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /*man---------------------------------------------------------------------------
  5. NAME
  6.      btree - B-tree file management library
  7.  
  8. SYNOPSIS
  9.      #include <btree.h>
  10.  
  11. DESCRIPTION
  12.      The btree library consists of a set of routines for the creation
  13.      and manipulation of file-based B-tree structures.  The B+-tree
  14.      variety of B-tree is used to provide efficient sequential as well
  15.      as random access.
  16.  
  17.      btree uses the blkio library for file access and buffering.
  18.      bexit should therefore be used in place of exit.
  19.  
  20. SEE ALSO
  21.      btclose, btcreate, btcursor, btdelcur, btdelete, btfirst, btfix,
  22.      btgetcur, btgetk, btgetlck, btinsert, btkeycmp, btkeycnt,
  23.      btkeysize, btlast, btlock, btnext, btopen, btprev, btsearch,
  24.      btsetbuf, btsetcur, btsetvbuf, btsync.
  25.  
  26. ------------------------------------------------------------------------------*/
  27. #ifndef H_BTREE        /* prevent multiple includes */
  28. #define H_BTREE
  29.  
  30. /* #ident    "@(#)btree.h    1.5 - 91/09/23" */
  31.  
  32. #include <ansi.h>
  33.  
  34. /* ansi headers */
  35. #ifdef AC_STDDEF
  36. #include <stddef.h>
  37. #endif
  38.  
  39. /* library headers */
  40. #include <blkio.h>
  41.  
  42. /* constants */
  43. #define BTOPEN_MAX    BOPEN_MAX    /* max # btrees open at once */
  44. #define BTBUFCNT    ((size_t)12)    /* default # of nodes to buffer */
  45.  
  46. /* macro to calculate buffer size needed by a btree */
  47. #define    BTBUFSIZ(M, KEYSIZE, BUFCNT) ((size_t)(                \
  48.     sizeof(bthdr_t) +                        \
  49.     (BUFCNT) * (                            \
  50.         offsetof(btnode_t, keyv) +                \
  51.         ((M) - 1) * (KEYSIZE) +                    \
  52.         (M) * sizeof(bpos_t)                    \
  53.     )                                \
  54. ))
  55.  
  56. /* type definitions */
  57. typedef struct {        /* btree position */
  58.     bpos_t    node;        /* block number of node */
  59.     int    key;        /* key number in node */
  60. } btpos_t;
  61.  
  62. /* pointer to field comparison function */
  63. #ifdef AC_PROTO
  64. typedef int (*btcmp_t)(const void *p1, const void *p2, size_t n);
  65. #else
  66. typedef int (*btcmp_t)();
  67. #endif
  68.  
  69. typedef struct {        /* btree node */
  70.     bpos_t    lsib;        /* block number of left sibling */
  71.     bpos_t    rsib;        /* block number of right sibling */
  72.     int    n;        /* number keys in node  (n <= (m - 1)) */
  73.     void *    keyv;        /* pointer to m keys */
  74.     bpos_t *childv;        /* pointer to (m + 1) child block numbers */
  75. } btnode_t;
  76.  
  77. typedef struct {        /* btree file header */
  78.     bpos_t    flh;        /* position of free list head */
  79.     int    m;        /* order of tree */
  80.     size_t    keysize;    /* key size */
  81.     int    flags;        /* flags */
  82.     bpos_t    root;        /* position of root node */
  83.     bpos_t    first;        /* position of first leaf node */
  84.     bpos_t    last;        /* position of last leaf node */
  85.     unsigned long keycnt;    /* number keys currently in btree */
  86.     unsigned long height;    /* current height of btree */
  87. } bthdr_t;
  88.  
  89. typedef struct {        /* field definition */
  90.     size_t    offset;        /* offset of field in key */
  91.     size_t    len;        /* length of field */
  92.     btcmp_t    cmp;        /* comparison function */
  93.     int    flags;        /* flags */
  94. } btfield_t;
  95.  
  96. typedef struct {        /* btree control structure */
  97.     bthdr_t    bthdr;        /* header record */
  98.     BLKFILE *bp;        /* block file */
  99.     int    flags;        /* status flags */
  100.     int    fldc;        /* number of fields */
  101.     btfield_t *fldv;    /* field definitions */
  102.     btpos_t    cbtpos;        /* current btree position */
  103.     btnode_t *cbtnp;    /* current node */
  104.     btpos_t *sp;        /* search path to current position */
  105. } btree_t;
  106.  
  107. /* btfield_t bit flags */
  108. #define BT_FFLAGS    (3)        /* mask for all flags */
  109. #define BT_FASC        (1)        /* ascending order */
  110. #define BT_FDSC        (2)        /* descending order */
  111.  
  112. /* function declarations */
  113. #ifdef AC_PROTO
  114. int        btclose(btree_t *btp);
  115. int        btcreate(const char *filename, int m, size_t keysize,
  116.             int fldc, const btfield_t fldv[]);
  117. int        btdelcur(btree_t *btp);
  118. int        btdelete(btree_t *btp, const void *buf);
  119. int        btfirst(btree_t *btp);
  120. int        btfix(const char *filename, int m, size_t keysize,
  121.             int fldc, const btfield_t fldv[]);
  122. int        btgetcur(btree_t *btp, btpos_t *btposp);
  123. int        btgetk(btree_t *btp, void *buf);
  124. int        btgetlck(btree_t *btp);
  125. int        btinsert(btree_t *btp, const void *buf);
  126. int        btkeycmp(btree_t *btp, const void *buf1, const void *buf2);
  127. int        btlast(btree_t *btp);
  128. int        btlock(btree_t *btp, int ltype);
  129. int        btnext(btree_t *btp);
  130. btree_t *    btopen(const char *filename, const char *type,
  131.             int fldc, const btfield_t fldv[]);
  132. int        btprev(btree_t *btp);
  133. int        btsearch(btree_t *btp, const void *buf);
  134. int        btsetbuf(btree_t *btp, void *buf);
  135. int        btsetcur(btree_t *btp, const btpos_t *btposp);
  136. int        btsetvbuf(btree_t *btp, void *buf, size_t bufcnt);
  137. int        btsync(btree_t *btp);
  138. #else
  139. int        btclose();
  140. int        btcreate();
  141. int        btdelcur();
  142. int        btdelete();
  143. int        btfirst();
  144. int        btfix();
  145. int        btgetcur();
  146. int        btgetk();
  147. int        btgetlck();
  148. int        btinsert();
  149. int        btkeycmp();
  150. int        btlast();
  151. int        btlock();
  152. int        btnext();
  153. btree_t *    btopen();
  154. int        btprev();
  155. int        btsearch();
  156. int        btsetbuf();
  157. int        btsetcur();
  158. int        btsetvbuf();
  159. int        btsync();
  160. #endif    /* #ifdef AC_PROTO */
  161.  
  162. /* macros */
  163. #define    btcursor(BTP) ((void *)(                    \
  164.         (BTP)->cbtpos.node == NIL ? NULL : ((char *)NULL + 1)    \
  165. ))
  166. #define    btkeycnt(BTP)    ((BTP)->bthdr.keycnt)
  167. #define    btkeysize(BTP)    ((BTP)->bthdr.keysize)
  168.  
  169. /* lock types */
  170. #define BT_UNLCK    (0)    /* unlock */
  171. #define BT_RDLCK    (1)    /* read lock */
  172. #define BT_WRLCK    (2)    /* write lock */
  173. #define BT_RDLKW    (3)    /* read lock, wait */
  174. #define BT_WRLKW    (4)    /* write lock, wait */
  175.  
  176. /* error codes */
  177. #define BTEOS        (-40)        /* start of btree error code domain */
  178. #define BTEMFILE    (BTEOS - 1)    /* too many open btrees */
  179. #define BTECORRUPT    (BTEOS - 2)    /* btree is corrupt */
  180. #define BTENOPEN    (BTEOS - 3)    /* btree is not open */
  181. #define BTENBUF        (BTEOS - 4)    /* buffering is off */
  182. #define BTELOCK        (BTEOS - 5)    /* incorrect lock type */
  183. #define BTENKEY        (BTEOS - 6)    /* no key */
  184. #define BTEDUP        (BTEOS - 7)    /* duplicate key */
  185. #define BTEEOF        (BTEOS - 8)    /* past end of file */
  186. #define BTEPANIC    (BTEOS - 9)    /* internal btree error */
  187.  
  188. #endif        /* #ifndef BTREE_H */
  189.